GGH Encryption Scheme

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme.

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem can be a hard problem. This system was published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi, and uses a trapdoor one-way function which relies on the difficulty of lattice reduction. The idea included in this trapdoor function is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. But to return from this erroneous vector to the original lattice point a special basis is needed.

The GGH encryption scheme was cryptanalyzed (broken) in 1999 by . Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

Operation

GGH involves a ''private key'' and a ''public key''.

The private key is a basis $B$ of a lattice $L$ with good properties (such as short nearly orthogonal vectors) and a unimodular matrix $U$.

The public key is another basis of the lattice $L$ of the form $B'=UB$.

For some chosen M, the message space consists of the vector $(m_1,..., m_n)$ in the range -M .

Encryption

Given a message $m = (m_1,..., m_n)$, error $e$, and a
public key $B'$ compute

: $v = \sum m_i b_i'$

In matrix notation this is

: $v=m\cdot B'$.

Remember $m$ consists of integer values, and $b'$ is a lattice point, so v is also a lattice point. The ciphertext is then

: $c=v+e=m \cdot B' + e$

Decryption

To decrypt the ciphertext one computes

: $c \cdot B^ = (m\cdot B^\prime +e)B^ = m\cdot U\cdot B\cdot B^ + e\cdot B^ = m\cdot U + e\cdot B^$

The Babai rounding technique will be used to remove the term $e \cdot B^$ as long as it is small enough. Finally compute

: $m = m \cdot U \cdot U^$

to get the messagetext.

Example

Let $L \subset \mathbb^2$ be a lattice with the basis $B$ and its inverse $B^$

: $B= \begin 7 & 0 \\ 0 & 3 \\ \end$ and $B^= \begin \frac & 0 \\ 0 & \frac \\ \end$

With

: $U = \begin 2 & 3 \\ 3 &5\\ \end$ and
: $U^ = \begin 5 & -3 \\ -3 &2\\ \end$

this gives

: $B' = U B = \begin 14 & 9 \\ 21 & 15 \\ \end$

Let the message be $m = (3, -7)$ and the error vector $e = (1, -1)$. Then the ciphertext is

: $c = m B'+e=(-104, -79).\,$

To decrypt one must compute

: $c B^ = \left( \frac, \frac\right).$

This is rounded to $(-15, -26)$ and the message is recovered with

: $m= (-15, -26) U^ = (3, -7).\,$

Security of the scheme

In 1999, Nguyen Phon Nguyen. ''Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97''. CRYPTO, 1999 showed that the GGH encryption scheme has a flaw in the design. He showed that every ciphertext reveals information about the plaintext and that the problem of decryption could be turned into a special closest vector problem much easier to solve than the general CVP.

References

Bibliography

*
*
* {{cite journal , last1 = Nguyen , first1 = Phong Q. , last2 = Regev , first2 = Oded , title = Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, journal = Journal of Cryptology , date = 11 November 2008 , volume = 22 , issue = 2 , pages = 139–160 , issn = 0933-2790 , eissn = 1432-1378 , doi = 10.1007/s00145-008-9031-0 , pmid = , url = https://iacr.org/archive/eurocrypt2006/40040273/40040273.pdfPreliminary version in EUROCRYPT 2006.

Lattice-based cryptography
Public-key encryption schemes